<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 符合要求的元组的个数（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个整数数组 nums、一个数字k&#xff0c;一个整数目标值 target&#xff0c;请问nums中是否存在k个元素使得其相加结果为target&#xff0c;请输出所有符合条件且不重复的k元组的个数</p> 
<p></p> 
<p>数据范围</p> 
<ul><li>2 ≤ nums.length ≤ 200</li><li>-10^9 ≤ nums[i] ≤ 10^9</li><li>-10^9 ≤ target ≤ 10^9</li><li>2 ≤ k ≤ 100</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行是nums取值&#xff1a;2 7 11 15</p> 
<p>第二行是k的取值&#xff1a;2</p> 
<p>第三行是target取值&#xff1a;9</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出第一行是符合要求的元组个数&#xff1a;1</p> 
<p>补充说明&#xff1a;[2,7]满足&#xff0c;输出个数是1</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">-1 0 1 2 -1 -4<br /> 3<br /> 0</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">[-1,0,1]&#xff0c;[-1,-1,2]满足条件</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2 7 11 15<br /> 2<br /> 9</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">[2,7]符合条件</td></tr></tbody></table> 
<p></p> 
<h3 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析&#xff08;分治递归&#43;双指针&#xff09;</h3> 
<p>本题其实就是要求K数之和。</p> 
<p>本题的K数之和&#xff0c;和<a href="https://blog.csdn.net/qfc_128220/article/details/131133325?spm&#61;1001.2014.3001.5501" title="LintCode - 89 K数之和_伏城之外的博客-CSDN博客">LintCode - 89 K数之和_伏城之外的博客-CSDN博客</a>是存在区别的&#xff0c;</p> 
<p>本题的要求的K元组是从整数数组中选取的&#xff0c;这里的整数数组&#xff0c;既可能包含正数&#xff0c;也可能包含负数&#xff0c;也可能包含0&#xff0c;另外最终求得的符合要求的K元组&#xff0c;还要进行去重。</p> 
<p></p> 
<p>因此&#xff0c;本题无法参考&#xff1a;<a href="https://blog.csdn.net/qfc_128220/article/details/131133325?spm&#61;1001.2014.3001.5501" title="LintCode - 89 K数之和_伏城之外的博客-CSDN博客">LintCode - 89 K数之和_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<p>本题其实需要参考&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/131126492?spm&#61;1001.2014.3001.5501" title="LeetCode - 15 三数之和_伏城之外的博客-CSDN博客">LeetCode - 15 三数之和_伏城之外的博客-CSDN博客</a></p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/131132362?spm&#61;1001.2014.3001.5501" title="LeetCode - 18 四数之和_伏城之外的博客-CSDN博客">LeetCode - 18 四数之和_伏城之外的博客-CSDN博客</a></p> 
<p>这两题。如果你对这两题不熟悉&#xff0c;请做本题前&#xff0c;先做完前面这两题&#xff0c;这两题是基础。否则下面代码会看不懂。</p> 
<p></p> 
<p>其中三数之和&#xff0c;是需要固定三元组中的最小的一个值&#xff0c;然后通过双指针找到剩余两个数。</p> 
<p>其中四数之和&#xff0c;是需要固定四元组中的最小的两个值&#xff0c;然后通过双指针找到剩余两个数。</p> 
<p>而K数之和&#xff0c;其实需要固定K元组中最小的K-2个值&#xff0c;然后通过双指针找到剩余两个数。</p> 
<p></p> 
<p>因此&#xff0c;下面代码实现中分为了两部分&#xff1a;</p> 
<ol><li>K-2重for循环完成 K元组中最小的K-2个值的确定</li><li>通过双指针完成剩余两个值的确定</li></ol> 
<p>而实际上K的值是不确定的&#xff0c;因此第1部分的K-2重for循环需要通过递归完成。</p> 
<p></p> 
<p>具体请看下面代码实现。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 3) {
    const nums &#61; lines[0].split(&#34; &#34;).map(Number);
    const k &#61; parseInt(lines[1]);
    const target &#61; parseInt(lines[2]);

    console.log(getResult(nums, k, target));

    lines.length &#61; 0;
  }
});

function getResult(nums, k, target) {
  if (k &gt; nums.length) return 0;
  nums.sort((a, b) &#61;&gt; a - b);
  return kSum(nums, k, target, 0, 0, 0);
}

// k数之和
function kSum(nums, k, target, start, count, sum) {
  if (k &lt; 2) return count;

  if (k &#61;&#61; 2) {
    return twoSum(nums, target, start, count, sum);
  }

  for (let i &#61; start; i &lt;&#61; nums.length - k; i&#43;&#43;) {
    // 剪枝
    if (nums[i] &gt; 0 &amp;&amp; sum &#43; nums[i] &gt; target) break;

    // 去重
    if (i &gt; start &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;

    count &#61; kSum(nums, k - 1, target, i &#43; 1, count, sum &#43; nums[i]);
  }

  return count;
}

// 两数之和
function twoSum(nums, target, start, count, preSum) {
  let l &#61; start;
  let r &#61; nums.length - 1;

  while (l &lt; r) {
    const sum &#61; preSum &#43; nums[l] &#43; nums[r];

    if (sum &gt; target) {
      r--;
    } else if (sum &lt; target) {
      l&#43;&#43;;
    } else {
      count&#43;&#43;;
      // 去重
      while (l &#43; 1 &lt; r &amp;&amp; nums[l] &#61;&#61; nums[l &#43; 1]) l&#43;&#43;;
      // 去重
      while (r - 1 &gt; l &amp;&amp; nums[r] &#61;&#61; nums[r - 1]) r--;
      l&#43;&#43;;
      r--;
    }
  }

  return count;
}
</code></pre> 
<h4 id="Java%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int[] nums &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
    int k &#61; Integer.parseInt(sc.nextLine());
    int target &#61; Integer.parseInt(sc.nextLine());

    System.out.println(getResult(nums, k, target));
  }

  public static int getResult(int[] nums, int k, int target) {
    if (k &gt; nums.length) return 0;
    Arrays.sort(nums);
    return kSum(nums, k, target, 0, 0, 0);
  }

  // k数之和
  public static int kSum(int[] nums, int k, int target, int start, int count, long sum) {
    if (k &lt; 2) return count;

    if (k &#61;&#61; 2) {
      return twoSum(nums, target, start, count, sum);
    }

    for (int i &#61; start; i &lt;&#61; nums.length - k; i&#43;&#43;) {
      // 剪枝
      if (nums[i] &gt; 0 &amp;&amp; sum &#43; nums[i] &gt; target) break;

      // 去重
      if (i &gt; start &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;
      count &#61; kSum(nums, k - 1, target, i &#43; 1, count, sum &#43; nums[i]);
    }

    return count;
  }

  // 两数之和
  public static int twoSum(int[] nums, int target, int start, int count, long preSum) {
    int l &#61; start;
    int r &#61; nums.length - 1;

    while (l &lt; r) {
      long sum &#61; preSum &#43; nums[l] &#43; nums[r];

      if (target &lt; sum) {
        r--;
      } else if (target &gt; sum) {
        l&#43;&#43;;
      } else {
        count&#43;&#43;;
        // 去重
        while (l &#43; 1 &lt; r &amp;&amp; nums[l] &#61;&#61; nums[l &#43; 1]) l&#43;&#43;;
        // 去重
        while (r - 1 &gt; l &amp;&amp; nums[r] &#61;&#61; nums[r - 1]) r--;
        l&#43;&#43;;
        r--;
      }
    }

    return count;
  }
}
</code></pre> 
<h4 id="Python%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81" style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
nums &#61; list(map(int, input().split()))
k &#61; int(input())
target &#61; int(input())


# 两数之和
def twoSum(nums, target, start, count, preTotal):
    l &#61; start
    r &#61; len(nums) - 1

    while l &lt; r:
        total &#61; preTotal &#43; nums[l] &#43; nums[r]

        if target &lt; total:
            r -&#61; 1
        elif target &gt; total:
            l &#43;&#61; 1
        else:
            count &#43;&#61; 1
            # 去重
            while l &#43; 1 &lt; r and nums[l] &#61;&#61; nums[l &#43; 1]:
                l &#43;&#61; 1
            # 去重
            while r - 1 &gt; l and nums[r] &#61;&#61; nums[r - 1]:
                r -&#61; 1
            l &#43;&#61; 1
            r -&#61; 1

    return count


# k数之和
def kSum(nums, k, target, start, count, total):
    if k &lt; 2:
        return count

    if k &#61;&#61; 2:
        return twoSum(nums, target, start, count, total)

    for i in range(start, len(nums) - k &#43; 1):
        # 剪枝
        if nums[i] &gt; 0 and total &#43; nums[i] &gt; target:
            break

        # 去重
        if i &gt; start and nums[i] &#61;&#61; nums[i - 1]:
            continue
        count &#61; kSum(nums, k - 1, target, i &#43; 1, count, total &#43; nums[i])

    return count


# 算法入口
def getResult():
    if k &gt; len(nums):
        return 0

    nums.sort()
    return kSum(nums, k, target, 0, 0, 0)


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_SIZE 200

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

int getResult(int nums[], int nums_size, int k, int target);

int kSum(const int nums[], int nums_size, int k, int target, int start, int count, long sum);

int twoSum(const int nums[], int nums_size, int target, int start, int count, long preSum);

int main() {
    int nums[MAX_SIZE];
    int nums_size &#61; 0;

    while (scanf(&#34;%d&#34;, &amp;nums[nums_size&#43;&#43;])) {
        if (getchar() !&#61; &#39; &#39;) break;
    }

    int k;
    scanf(&#34;%d&#34;, &amp;k);

    int target;
    scanf(&#34;%d&#34;, &amp;target);

    printf(&#34;%d\n&#34;, getResult(nums, nums_size, k, target));

    return 0;
}

int getResult(int nums[], int nums_size, int k, int target) {
    if (k &gt; nums_size) return 0;

    qsort(nums, nums_size, sizeof(int), cmp);

    return kSum(nums, nums_size, k, target, 0, 0, 0);
}

// k数之和
int kSum(const int nums[], int nums_size, int k, int target, int start, int count, long sum) {
    if (k &lt; 2) return count;

    if (k &#61;&#61; 2) {
        return twoSum(nums, nums_size, target, start, count, sum);
    }

    for (int i &#61; start; i &lt;&#61; nums_size - k; i&#43;&#43;) {
        // 剪枝
        if (nums[i] &gt; 0 &amp;&amp; sum &#43; nums[i] &gt; target) break;

        // 去重
        if (i &gt; start &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;
        count &#61; kSum(nums, nums_size, k - 1, target, i &#43; 1, count, sum &#43; nums[i]);
    }

    return count;
}

// 两数之和
int twoSum(const int nums[], int nums_size, int target, int start, int count, long preSum) {
    int l &#61; start;
    int r &#61; nums_size - 1;

    while (l &lt; r) {
        long sum &#61; preSum &#43; nums[l] &#43; nums[r];

        if (target &lt; sum) {
            r--;
        } else if (target &gt; sum) {
            l&#43;&#43;;
        } else {
            count&#43;&#43;;

            // 去重
            while (l &#43; 1 &lt; r &amp;&amp; nums[l] &#61;&#61; nums[l &#43; 1]) l&#43;&#43;;
            // 去重
            while (r - 1 &gt; l &amp;&amp; nums[r] &#61;&#61; nums[r - 1]) r--;

            l&#43;&#43;;
            r--;
        }
    }

    return count;
}</code></pre> 
<p></p> 
<h3>题目解析&#xff08;回溯算法&#43;组合求解&#xff09;</h3> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const nums &#61; (await readline()).split(&#34; &#34;).map(Number);
  const k &#61; parseInt(await readline());
  const target &#61; parseInt(await readline());

  let ans &#61; 0;

  /**
   * 回溯算法 组合求解
   * &#64;param {*} index 当前树层选取元素的起始位置&#xff0c;每次递归就是一层
   * &#64;param {*} total 组合内元素之和
   * &#64;param {*} count 组合内元素个数
   */
  function dfs(index, total, count) {
    // 组合内元素个数达到k个时
    if (count &#61;&#61; k) {
      // 检查组合内元素之和是否为target
      if (total &#61;&#61; target) {
        // 若是&#xff0c;则符合要求的元组个数&#43;1
        ans&#43;&#43;;
      }
      return;
    }

    for (let i &#61; index; i &lt; nums.length; i&#43;&#43;) {
      // 树层去重
      if (i &gt; index &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;
      // 回溯逻辑已隐含
      dfs(i &#43; 1, total &#43; nums[i], count &#43; 1);
    }
  }

  nums.sort((a, b) &#61;&gt; a - b);
  dfs(0, 0, 0);
  console.log(ans);
})();
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;

public class Main {
  static int[] nums;
  static int k;
  static int target;
  static int ans &#61; 0;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    nums &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
    k &#61; Integer.parseInt(sc.nextLine());
    target &#61; Integer.parseInt(sc.nextLine());

    System.out.println(getResult());
  }

  public static int getResult() {
    Arrays.sort(nums);
    dfs(0, 0, 0);
    return ans;
  }

  /**
   * 回溯算法 组合求解
   *
   * &#64;param index 当前树层选取元素的起始位置&#xff0c;每次递归就是一层
   * &#64;param total 组合内元素之和
   * &#64;param count 组合内元素个数
   */
  public static void dfs(int index, long total, int count) {
    // 组合内元素个数达到k个时
    if (count &#61;&#61; k) {
      // 检查组合内元素之和是否为target
      if (total &#61;&#61; target) {
        // 若是&#xff0c;则符合要求的元组个数&#43;1
        ans &#43;&#61; 1;
      }
      return;
    }

    for (int i &#61; index; i &lt; nums.length; i&#43;&#43;) {
      // 树层去重
      if (i &gt; index &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) continue;
      // 回溯逻辑已隐含
      dfs(i &#43; 1, total &#43; nums[i], count &#43; 1);
    }
  }
}
</code></pre> 
<h4 style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python">nums &#61; list(map(int, input().split()))
k &#61; int(input())
target &#61; int(input())

ans &#61; 0


def dfs(index, total, count):
    &#34;&#34;&#34;
    回溯算法 组合求解
    :param index: 当前树层选取元素的起始位置&#xff0c;每次递归就是一层
    :param total: 组合内元素之和
    :param count: 组合内元素个数
    &#34;&#34;&#34;
    global ans

    # 组合内元素个数达到k个时
    if count &#61;&#61; k:
        # 检查组合内元素之和是否为target
        if total &#61;&#61; target:
            # 若是&#xff0c;则符合要求的元组个数&#43;1
            ans &#43;&#61; 1
        return

    for i in range(index, len(nums)):
        # 树层去重
        if i &gt; index and nums[i] &#61;&#61; nums[i - 1]:
            continue

        # 回溯逻辑已隐含
        dfs(i &#43; 1, total &#43; nums[i], count &#43; 1)


def result():
    nums.sort()
    dfs(0, 0, 0)
    return ans


print(result())
</code></pre> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_SIZE 200

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}
int getResult(int nums[], int nums_size, int k, int target);
void dfs(const int nums[], int nums_size, int k, int target, int index, long total, int count, int* ans);

int main() {
    int nums[MAX_SIZE];
    int nums_size &#61; 0;

    while (scanf(&#34;%d&#34;, &amp;nums[nums_size&#43;&#43;])) {
        if (getchar() !&#61; &#39; &#39;) break;
    }

    int k;
    scanf(&#34;%d&#34;, &amp;k);

    int target;
    scanf(&#34;%d&#34;, &amp;target);


    printf(&#34;%d\n&#34;, getResult(nums, nums_size, k, target));

    return 0;
}

int getResult(int nums[], int nums_size, int k, int target) {
    int ans &#61; 0;

    qsort(nums, nums_size, sizeof(int), cmp);
    dfs(nums, nums_size, k, target, 0, 0, 0, &amp;ans);

    return ans;
}

void dfs(const int nums[], int nums_size, int k, int target, int index, long total, int count, int* ans) {
    // 组合内元素个数达到k个时
    if (count &#61;&#61; k) {
        // 检查组合内元素之和是否为target
        if (total &#61;&#61; target) {
            // 若是&#xff0c;则符合要求的元组个数&#43;1
            (*ans)&#43;&#43;;
        }

        return;
    }

    for (int i &#61; index; i &lt; nums_size; i&#43;&#43;) {
        // 树层去重
        if (i &gt; index &amp;&amp; nums[i] &#61;&#61; nums[i - 1]) {
            continue;
        }

        // 回溯
        dfs(nums, nums_size, k, target, i &#43; 1, total &#43; nums[i], count &#43; 1, ans);
    }
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>